package com.zhujy.test;

public class MedianOfArray {
	public static void main(String[] args) {
		MedianOfArray test = new MedianOfArray();
		int nums1[] = {1,2};
		int nums2[] = {3};
		double res = test.findMedianSortedArrays(nums1, nums2);
		System.out.println(res);
	}
	
	
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		if(nums1.length > nums2.length) {
			int[] temp = nums1;
			nums1 = nums2;
			nums2 = temp;
		}
		int mL = nums1.length;
        int nL = nums2.length;
        int mid = (mL+nL+1)/2;
        int iMin = 0;
        int iMax = mL;
        while (iMin<iMax) {
			int i = (iMin+iMax)/2;
			int j = mid - i;
			if(i<iMax && nums2[j-1]>nums1[i]) {
				iMin = i+1;
			}else if(i>iMin && nums1[i-1]>nums2[j]) {
				iMax = i-1;
			}else {
				double maxL = 0,minR = 0;
				if(i == 0) {
					maxL = nums2[j-1];
				}else if(j==0) {
					maxL = nums1[i-1];
				}else {
					maxL = Math.max(nums1[i-1], nums2[j-1]);
				}
				
				if((mL+nL)%2 == 1) {
					return maxL;
				}
				
				if(i == mL) {
					minR = nums2[j];
				}else if(j==nL) {
					minR = nums1[i];
				}else {
					maxL = Math.min(nums1[i], nums2[j]);
				}
				
				return (minR+maxL)/2.0;
			}
		}
        
        return 0.0;
    }
}
